11067 - Little red riding hood/11067.cpp

   1 #include <iostream>
   2
   3 using namespace std;
   4
   5 unsigned int dp[101][101];
   6 bool wolf[101][101];
   7
   8
   9 int main(){
  10   int w, h;
  11   while (cin >> w >> h && w && h){
  12     for (int i=0; i<=w; ++i){
  13       for (int j=0; j<=h; ++j){
  14         dp[i][j] = wolf[i][j] = 0;
  15       }
  16     }
  17     int wolves;
  18     cin >> wolves;
  19     while (wolves--){
  20       int i, j;
  21       cin >> i >> j;
  22       wolf[i][j] = true;
  23     }
  24
  25     dp[0][0] = 1;
  26     for (int i=0; i<=w; ++i){
  27       for (int j=0; j<=h; ++j){
  28         if (!wolf[i][j]){
  29           if (i > 0) dp[i][j] += dp[i-1][j];
  30           if (j > 0) dp[i][j] += dp[i][j-1];
  31         }
  32       }
  33     }
  34
  35     int t = dp[w][h];
  36     if (t == 0){
  37       cout << "There is no path." << endl;
  38     }else{
  39       cout << "There ";
  40       if (t == 1) cout << "is one path";
  41       else cout << "are " << t << " paths";
  42       cout << " from Little Red Riding Hood's house to her grandmother's house." << endl;
  43     }
  44
  45   }
  46   return 0;
  47 }